package stu.day39_day.day39;

import java.util.Arrays;

public class hw4 {
    public int lengthOfLIS(int[] nums) {

        int len = nums.length;
        int[] dp = new int[len];

        dp[0]=1;
        for(int i=0;i<len;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            dp[i] = Math.max(dp[i],1);
        }

        return Arrays.stream(dp).max().getAsInt();
    }

    public boolean increasingTriplet(int[] nums) {
        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;

        for(int i=0;i<nums.length;i++){
            if(nums[i]>second){
                return true;
            }else if(nums[i]<=first){
                first = nums[i];
            }else {
                second = nums[i];
            }


        }


        return false;
    }

    public int findNumberOfLIS(int[] nums) {

        int len = nums.length;
        int[] dp = new int[len];
        int[][] arr = new int[len][len+1];
        Arrays.fill(dp,1);
        //arr[1] = len;
        for(int i=0;i<len;i++){
            arr[i][1] = 1;
        }

        int max = 0;
        int index = 0;
        for(int i=0;i<len;i++){
            for (int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    index = dp[j]+1;
                    arr[i][index] += arr[j][dp[j]];
                    dp[i] = Math.max(dp[i],index);
                }
            }
            max = Math.max(max,dp[i]);
        }

        int sum = 0;
        for(int i=0;i<len;i++){
            sum += arr[i][max];
        }

        return sum;
    }




}
